﻿#pragma once

#include <iostream>
#include <vector>
#include <unordered_map>
#include <map>
#include <algorithm>

#include <time.h>
#include <assert.h>

#include <thread>
#include <mutex>
#include <atomic>

using std::cout;
using std::endl;

#ifdef _WIN32
#include <Windows.h>
#elif
// ...
#endif

using std::cout;
using std::endl;

static const size_t MAX_BYTES = 256 * 1024; // 存储的最大字节数
static const size_t N_FREELIST = 208; // 自由链表的桶数，每个桶代表不同的字节大小，经计算得出
static const size_t N_PAGES = 129;    // 页的个数，在pageCache中，哈希的下标表示该桶中span的大小
static const size_t PAGE_SHIFT = 13;  // 页大小就是8k，也就是13位比特位

// 直接去堆上按⻚申请空间
inline static void* SystemAlloc(size_t kpage)
{
#ifdef _WIN32
	void* ptr = VirtualAlloc(0, kpage * (1 << 13), MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	// linux下brk mmap等
#endif
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}
// 释放堆开辟的空间
inline static void SystemFree(void* ptr)
{
#ifdef _WIN32
	VirtualFree(ptr, 0, MEM_RELEASE);
#else
	// sbrk unmmap等
#endif
}

// 防止在不同机器下，页数大小不一致导致的溢出
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#elif _WIN32
typedef size_t PAGE_ID;
#else 
// linux...
#endif

// 获取obj下一个节点的地址
// void*& NextObj(void*& obj); 
// 不需要给参数进行引用，因为我们修改的是obj所指向的空间内容，而不是obj的内容
static void*& NextObj(void* obj)
{
	return *(void**)obj;
}

// 管理切分好的小对象的自由链表
class FreeList
{
public:
	// 头插
	inline void Push(void* obj)
	{
		assert(obj);

		NextObj(obj) = _freeList;
		_freeList = obj;
		++_size;
	}
	inline void PushRange(void* start, void* end, size_t n)
	{
		assert(start);

		NextObj(end) = _freeList;
		_freeList = start;
		_size += n;
	}
	// 头删
	inline void* Pop()
	{
		assert(_freeList);

		void* obj = _freeList;
		_freeList = NextObj(_freeList);
		--_size;
		return obj;
	}
	inline void PopRange(void*& start, void*& end, size_t n)
	{
		assert(n >= _size);

		start = _freeList;
		end = start;
		for (int i = 0; i < n - 1; ++i)
		{
			end = NextObj(end);
		}

		_freeList = NextObj(end);
		NextObj(end) = nullptr;
		_size -= n;
	}
	// 判断是否为空
	inline bool Empty()
	{
		return _freeList == nullptr;
	}
	inline size_t& MaxSize()
	{
		return _maxSize;
	}
	inline size_t Size()
	{
		return _size;
	}
private:
	void* _freeList = nullptr;
	size_t _maxSize = 1;
	size_t _size = 0;
};

// 计算对象大小的映射规则
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎片浪费
	// [1,128]				8byte对⻬			freelist[0,16)
	// [128+1,1024]			16byte对⻬			freelist[16,72)
	// [1024+1,8*1024]		128byte对⻬			freelist[72,128)
	// [8*1024+1,64*1024]	1024byte对⻬			freelist[128,184)
	// [64*1024+1,256*1024] 8*1024byte对⻬		freelist[184,208)

	// 对齐大小计算
	// 会把用户申请的size值进行向上取整成一个合适的值
	static inline size_t RoundUp(size_t size)
	{
		int objSize = 0;
		if (size <= 128)
		{
			objSize = _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			objSize = _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			objSize = _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			objSize = _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			objSize = _RoundUp(size, 8*1024);
		}
		else
		{
			objSize = _RoundUp(size, 1 << PAGE_SHIFT);
		}

		return objSize;
	}
	// 计算用户申请的内存大小对齐后的内存大小对应的哈希桶的位置
	static inline size_t Index(size_t size)
	{
		int objSize = 0;
		int group[] = { 16, 56 ,56, 56 };

		if (size <= 128)
		{
			objSize = _Index(size, 8);
		}
		else if (size <= 1024)
		{
			objSize = _Index(size - 128, 16) + group[0];
		}
		else if (size <= 8 * 1024)
		{
			objSize = _Index(size - 1024, 128) + group[1];
		}
		else if (size <= 64 * 1024)
		{
			objSize = _Index(size - 8 * 1024, 1024) + group[2];
		}
		else if (size <= 256 * 1024)
		{
			objSize = _Index(size - 64* 1024, 8 * 1024) + group[3];
		}
		else
		{
			assert(false);
		}

		return objSize;
	}
	// 一次ThreadCache从CentralCache获得多少内存
	static inline size_t NumMoveSize(size_t size)
	{
		assert(size > 0);
		// [2, 512]，一次批量移动多少个对象的(慢启动)上限值

		int num = MAX_BYTES / size;
		
		if (num < 2)
			num = 2;

		if (num > 512)
			num = 512;

		return num;
	}
	// 一次CentralCache从PageCache获得多少内存, 页
	static inline size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size; // 总的一次总内存 -- 字节

		npage >>= PAGE_SHIFT; // 总的一次总内存 -- 页

		if (npage == 0) npage = 1;

		return npage;
	}
private:
	static inline size_t _RoundUp(size_t size, int alignNum)
	{
		if (size % alignNum != 0)
			return (size / alignNum + 1) * alignNum;
		else
			return alignNum;
	}
	static inline size_t _Index(size_t size, int alignNum)
	{
		if (size % alignNum == 0)
		{
			return size / alignNum - 1;
		}
		else
		{
			return size / alignNum;
		}
	}
}; 


// 管理多个连续页大块内存跨度结构
struct Span
{
	// 在32位下，size_t可以，但是在64位下，size_t存不下
	PAGE_ID _pageId = 0; // 大号内存起始的页号
	size_t _n = 0;	     //	页的数量

	// 双向链表结构
	Span* _next = nullptr;
	Span* _prev = nullptr;

	size_t _useCount = 0; // 切好小块内存，被分配给ThreadCache的计数
	size_t _objSize = 0; // 切好小对象的大小
	void* _freeList = nullptr;  // 切好小块内存，但是没有被分配的自由链表

	bool _isUsed = false; // 是否span正在被使用
};
// 带头双向循环链表
class SpanList 
{
public:
	inline SpanList()
	{
		_head = new Span;
		_head->_next = _head;
		_head->_prev = _head;
	}
	inline bool Empty()
	{
		return _head->_next == _head;
	}
	inline Span* Begin()
	{
		return _head->_next;
	}
	inline Span* End()
	{
		return _head;
	}
	inline void PushFront(Span* span)
	{
		Insert(Begin(), span); 
	}
	inline Span* PopFront()
	{
		Span* cur = _head->_next;

		/*_head->_next = cur->_next;
		cur->_next->_prev = _head;*/
		Erase(cur);

		return cur;
	}
	// 插入newSpan到pos的前一个位置
	inline void Insert(Span* pos, Span* newSpan)
	{
		assert(pos);
		assert(newSpan);

		newSpan->_next = pos;
		newSpan->_prev = pos->_prev;
		pos->_prev->_next = newSpan;
		pos->_prev = newSpan;
	}
	// 删除pos位置的Span
	inline void Erase(Span* pos)
	{
		assert(pos);
		assert(pos != _head);

		pos->_prev->_next = pos->_next;
		pos->_next->_prev = pos->_prev;
	}
private:
	Span* _head;
public:
	std::mutex _mtx; // 桶锁
};